package 力扣;

import java.util.*;

/**
 * @author ZhuYi
 * @create 2025/4/1 16:42
 */
public class 前k个高频元素_347 {
    public static void main(String[] args) {
        int[] nums = {1, 1, 1, 2, 2, 3};
        int k = 2;
        System.out.println(Arrays.toString(topKFrequent(nums, k)));
    }

    public static int[] topKFrequent(int[] nums, int k) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int num : nums) {
            //map键存数字，值存出现的次数
            map.put(num, map.getOrDefault(num, 0) + 1);
        }
        Queue<int[]> queue = new PriorityQueue<>(new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[1] - o2[1];
            }
        });
        int ct1 = 0;
        //初始化小根堆
        for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
            int[] tmp = {entry.getKey(), entry.getValue()};
            queue.offer(tmp);
            if (++ct1 == k) break;
        }
        int ct2 = 0;
        //放入小根堆
        for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
            int key = entry.getKey();
            int value = entry.getValue();
            if (++ct2 > k) {
                if (value > queue.peek()[1] && key != queue.peek()[0]) {
                    queue.poll();
                    int[] arr = {key, value};
                    queue.offer(arr);
                }
            }

        }
        int[] res = new int[k];
        for (int i = 0; i < k; i++) {
            res[i] = queue.peek()[0];
            queue.poll();
        }
        return res;
    }


}
